/**
 * 
 */
package tree.passed;

import java.util.List;

/**
 * @author xyyi
 *
 */
public class PopulatingNextRightPointersInEachNode {

	/**
	Given a binary tree

	struct TreeLinkNode {
	  TreeLinkNode *left;
	  TreeLinkNode *right;
	  TreeLinkNode *next;
	}

	Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

	Initially, all next pointers are set to NULL.

	Note:

	You may only use constant extra space.
	You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

	For example,
	Given the following perfect binary tree,

	     1
	   /  \
	  2    3
	 / \  / \
	4  5  6  7

	After calling your function, the tree should look like:

	     1 -> NULL
	   /  \
	  2 -> 3 -> NULL
	 / \  / \
	4->5->6->7 -> NULL
	 */
	public void connect(TreeLinkNode root) {
		if (root == null)
			return;

		if (root.right != null && root.next != null)
			root.right.next = root.next.left;
		if (root.left != null)
			root.left.next = root.right;

		connect(root.right);
		connect(root.left);
	}

	/**
	Populating Next Right Pointers in Each Node II
	
	Follow up for problem "Populating Next Right Pointers in Each Node".

	What if the given tree could be any binary tree? Would your previous solution still work?

	Note:

	You may only use constant extra space.

	For example,
	Given the following binary tree,

	     1
	   /  \
	  2    3
	 / \    \
	4   5    7

	After calling your function, the tree should look like:

	     1 -> NULL
	   /  \
	  2 -> 3 -> NULL
	 / \    \
	4-> 5 -> 7 -> NULL
	 */
	/*
	[解题思路]
	与上一题类似，唯一的不同是每次要先找到一个第一个有效的next链接节点，并且递归的时候要先处理右子树，再处理左子树。
	 */

	/*
	 * http://discuss.leetcode.com/questions/282/populating-next-right-pointers-in-each-node-ii
	 * Best for interview
	 */
	public void connectI(TreeLinkNode root) {
		TreeLinkNode node = root;

		while (node != null) {
			TreeLinkNode nextLevel = null;
			TreeLinkNode preNode = null;
			while (node != null) {
				if (nextLevel == null) {
					nextLevel = node.left != null ? node.left : node.right;
				}

				if (node.left != null) {
					if (preNode != null)
						preNode.next = node.left;
					preNode = node.left;
				}

				if (node.right != null) {
					if (preNode != null)
						preNode.next = node.right;
					preNode = node.right;
				}

				node = node.next;
			}
			node = nextLevel;
		}
	}

	public void connectR(TreeLinkNode root) {
		if (root == null)
			return;

		TreeLinkNode next = root.next;
		while (next != null) {
			if (next.left != null) {
				next = next.left;
				break;
			}
			if (next.right != null) {
				next = next.right;
				break;
			}
			next = next.next;
		}

		if (root.right != null) {
			root.right.next = next;
		}

		if (root.left != null) {
			root.left.next = root.right != null ? root.right : next;
		}

		connect(root.right);
		connect(root.left);

	}

	public void connect2me(TreeLinkNode root) {
		if (root == null)
			return;

		TreeLinkNode node = root.right;
		if (root.left != null) {
			if (root.right != null) {
				root.left.next = root.right;
			} else {
				node = root.left;
			}
		}

		TreeLinkNode currNode = root.next;
		if (node != null) {
			while (currNode != null && currNode.left == null
			        && currNode.right == null) {
				currNode = currNode.next;
			}

			if (currNode != null) {
				if (currNode.left != null)
					node.next = currNode.left;
				else
					node.next = currNode.right;
			}
		}

		connect(root.right);
		connect(root.left);
	}

	/**
	 * Definition for binary tree with next pointer.
	 */
	public class TreeLinkNode {
		int val;
		TreeLinkNode left, right, next;

		TreeLinkNode(int x) {
			val = x;
		}
	}

	/*
	 * Best for general tree
	 */
	public void connectI(GTreeLinkNode root) {
		GTreeLinkNode node = root;
		while (node != null) {
			GTreeLinkNode nextLevel = null;
			GTreeLinkNode preNode = null;
			for (; node != null; node = node.next) {
				for (GTreeLinkNode n : node.children) {
					if (n != null) {
						if (nextLevel == null)
							nextLevel = n;
						if (preNode != null)
							preNode.next = n;
						preNode = n;
					}
				}
			}
			node = nextLevel;
		}
	}

	/**
	 * Definition for general tree with next pointer.
	 */
	public class GTreeLinkNode {
		int val;
		GTreeLinkNode next;
		List<GTreeLinkNode> children;

		GTreeLinkNode(int x) {
			val = x;
		}
	}

	/**
	 * 
	 */
	public PopulatingNextRightPointersInEachNode() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
